package 排序.桶排序;

import 排序.IArraySort;
import 排序.插入排序.InsertSort;

import java.util.Arrays;

/**
 * @author zc
 * @version 1.0
 * @date 2021/9/30 10:09
 */

//https://www.runoob.com/w3cnote/bucket-sort.html
public class BucketSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) {
        //return new int[0];
        int[] arr = Arrays.copyOf(sourceArray,sourceArray.length);

        return bucketSort(arr,5);
    }

    private int[] bucketSort(int[] arr ,int bucketSize){
        if (arr.length == 0){
            return arr;
        }
        int minValue = arr[0];
        int maxValue = arr[0];

        //找到最大值和最小值
        for (int value:arr) {
            if(value<minValue){
                minValue = value;
            }else if (value>maxValue){
                maxValue = value;
            }
        }

        //向下取整
        int bucketCount = (int)Math.floor((maxValue-minValue)/bucketSize)+1;
        int[][] buckets = new int[bucketCount][0];


        //利用映射函数将数据分配到各个桶中
        for (int i = 0; i < arr.length; i++) {
            int index = (int)Math.floor((arr[i] - minValue) / bucketSize);
            buckets[index] =  arrAppend(buckets[index],arr[i]);  //【核心】
            //把元素放到一个桶中
        }


        int arrIndex = 0;//重新从桶中把数据放回到数组中
        for (int [] bucket : buckets){
            if(bucket.length<=0){
                continue;
            }

            InsertSort insertSort = new InsertSort();
            //对每一个桶进行排序，这里是使用了插入排序
            bucket = insertSort.sort(bucket);

            for(int value :bucket){
                arr[arrIndex++]=value;
            }
        }

        return arr;

    }

    /**
     * 自动扩容，并且保存数据
     * @param arr
     * @param value
     * @return
     */
    private int[] arrAppend(int[] arr,int value){
        arr =Arrays.copyOf(arr,arr.length+1);
        arr[arr.length-1]=value;
        return arr;
    }


    public static void main(String[] args) {
        BucketSort bucketSort = new BucketSort();
        int[] a = {1,5,4,3,2,9,7,8};
        int[] sort = bucketSort.sort(a);
        for (int i : sort) {
            System.out.print(i+" ");
        }
    }
}
